package 八大排序;

/**
 * 直接插入排序：把新的数据插入到已经排好的数据列中。
 * @author 刘学松
 * @date 2021/2/24 19:27
 */
public class 直接插入排序 {
    public static void main(String[] args) {
        ArrayUtils.printArray(insertSort(ArrayUtils.array));
    }

    public static int[] insertSort(int[] a) {
        int length = a.length;
        int insertNum;

        for (int i = 1; i < length; i++) {
            insertNum = a[i];
            // j指向当前元素前一位
            int j = i - 1;
            while (j >= 0 && insertNum < a[j]) {
                // 往后移一位
                a[j + 1] = a[j];
                // 指针往前挪
                j--;
            }
            // 此时insertNum > a[j]，就在j+1的位置处插入
            a[j + 1] = insertNum;
        }

        return a;
    }
}
